/*
 * @(#)Pascal.java	1.0 Apr 26, 2008
 *
 *	The MIT License
 *
 *	Copyright (c) 2008 Malachi de AElfweald <malachid@gmail.com>
 *
 *	Permission is hereby granted, free of charge, to any person obtaining a copy
 *	of this software and associated documentation files (the "Software"), to deal
 *	in the Software without restriction, including without limitation the rights
 *	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 *	copies of the Software, and to permit persons to whom the Software is
 *	furnished to do so, subject to the following conditions:
 *
 *	The above copyright notice and this permission notice shall be included in
 *	all copies or substantial portions of the Software.
 *
 *	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 *	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 *	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 *	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 *	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 *	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 *	THE SOFTWARE.
 */
package org.eoti.math;

import java.math.BigInteger;

/**
 * Represents a row in Pascals' Triangle
 *
 * PRIMES: When should you use Pascal instead of the Sieve?
 *
 * Let's take an example... Starting at 1 as the first prime, the 7089th prime is 71563.
 *
 * Since the internal representation of the Pascal is a PalidromeArray, it will take 1/2 that
 * (or 35782) elements to maintain that number.
 *
 * Since the Sieve starts with a huge array and removes elements, it starts off with 71563 elements
 * in the array (twice the size of the Pascal) but ends up with an array that is 7089 elements (much
 * smaller).
 *
 * Speed-wise, the Sieve is much faster. However, you have to specify an upper boundary. If you want the
 * prime just above that, you have to pretty much start over.  With the Pascal, though it takes longer to
 * get there, you can navigate forward and backward freely.
 *
 * Overall, the Sieve takes more memory at first, the Pascal more memory at the end (though only 1/2 what the
 * Sieve starts with); and the Sieve will be faster if you know the highest number you will look at, while the
 * Pascal will be slower but let you navigate in both directions.
 */
public class Pascal
{
	public static Pascal ZERO = new Pascal(BigInteger.ONE);
	public static Pascal ONE = new Pascal(BigInteger.ONE,BigInteger.ONE);
	protected static BigInteger BI_TWO = BigInteger.valueOf(2);

	protected PalidromeArray ptLine;

	protected Pascal(PalidromeArray ptLine)
	{
		this.ptLine = ptLine;
	}

	protected Pascal(BigInteger ... ptLine)
	{
		this.ptLine = new PalidromeArray(ptLine);
	}

	public BigInteger getValue()
	{
		if(ptLine.totalLength().intValue() == 1) return BigInteger.ZERO;
		return ptLine.get(1);
	}

	public static Pascal fromArchivalString(String s)
	{
		String[] arr = s.split("\\|");
		BigInteger[] bi = new BigInteger[arr.length];
		for(int i=0; i<arr.length; i++)
			bi[i] = new BigInteger(arr[i]);

		return new Pascal(bi);
	}

	public String toArchivalString()
	{
		StringBuilder sb = new StringBuilder();
		boolean first = true;
		for(BigInteger bi : ptLine)
		{
			if(!first) sb.append("|");
			sb.append(bi.toString());
			first = false;
		}

		return sb.toString();
	}

	/**
	 * This one will do validation
	 */
	public static Pascal toPascal(BigInteger[] pascalTriangleLine)
	{
		if(pascalTriangleLine.length == 0)
			return null;
		if(pascalTriangleLine.length == 1)
			return Pascal.ZERO;

		BigInteger num = pascalTriangleLine[1];
		BigInteger sum = BigInteger.ZERO;
		for(BigInteger bi : pascalTriangleLine)
			sum = sum.add(bi);
		if(sum.equals(BI_TWO.pow(num.intValue())))// int value? eeks!
			return new Pascal(pascalTriangleLine);

		throw new NumberFormatException("The array does not hold a valid line of Pascal's Triangle");
	}

	public PalidromeArray toArray(){return ptLine;}

	public static Pascal toPascalUsingTriangle(BigInteger value, Pascal hint)
	{
		int compare = hint.getValue().compareTo(value);
		if(compare == 0)
			return hint;

		Pascal pascal = hint;
		if(compare < 0) // hint is less than value
		{
			while(!pascal.getValue().equals(value))
				pascal = pascal.nextPascal();
		}else{ // hint is more than value
			while(!pascal.getValue().equals(value))
				pascal = pascal.previousPascal();
		}
		return pascal;
	}

	public static Pascal toPascalUsingTriangle(BigInteger value)
	{
		return toPascalUsingTriangle(value, Pascal.ZERO);
	}

	public static Pascal toPascal(BigInteger value)
	{
		// gives us a chance to specify default implementation
		return toPascalUsingFractions(value);
	}

	public static Pascal toPascalUsingFractions(BigInteger value)
	{
		PalidromeArray cols = new PalidromeArray(value.add(BigInteger.ONE));
		BigInteger dividend = BigInteger.ONE;
		BigInteger divisor = BigInteger.ONE;
		BigInteger biCol = null;
		cols.set(0, BigInteger.ONE);
		int center = value.intValue()/2;
		for(int col=1; col<=center; col++)
		{
			biCol = BigInteger.valueOf(col);
			dividend = dividend.multiply(value.subtract(biCol.subtract(BigInteger.ONE)));
			divisor = divisor.multiply(biCol);
			cols.set(col, dividend.divide(divisor));
		}

		return new Pascal(cols);
	}

	public static Pascal toPascalUsingFactorials(BigInteger value)
	{
		if(value.equals(BigInteger.ZERO)) return Pascal.ZERO;
		if(value.equals(BigInteger.ONE)) return Pascal.ONE;

		/**
		 * binomial coefficient
		 * http://upload.wikimedia.org/math/6/f/4/6f481c5daf8fcb299d23c41262604296.png
		 * with n=row and k=col
		 */
		BigInteger dividendFAC = MathUtil.factorial(value);
		// don't like using ints here... might have to change to using ArrayList
		int rows = value.intValue();
		PalidromeArray cols = new PalidromeArray(value.add(BigInteger.ONE));

		cols.set(0, BigInteger.ONE);
		cols.set(1, value);
		if(rows == 2) return new Pascal(cols);
		cols.set(2, cols.get(1).multiply(cols.get(1).subtract(BigInteger.ONE)).divide(BI_TWO));//  (n*(n-1))/2
		if(rows <= 5) return new Pascal(cols); // we already generated 0-3 via mirror

		int center = rows/2;
		BigInteger lowFAC = null;
		BigInteger highFAC = null;
		BigInteger biCol = null;
		for(int lowCol=center; lowCol>2; lowCol--)
		{
			biCol = BigInteger.valueOf(lowCol);
			if(lowFAC == null)
			{
				lowFAC = MathUtil.factorial(biCol);
				highFAC = MathUtil.factorial(value.subtract(biCol));
			}else{
				lowFAC = lowFAC.divide(biCol.add(BigInteger.ONE));
				highFAC = highFAC.multiply(value.subtract(biCol));
			}

//			System.out.println("cols.set("+lowCol+","+dividendFAC+".divideFAC("+lowFAC+".multiply("+highFAC+")))");
			cols.set(lowCol, dividendFAC.divide(lowFAC.multiply(highFAC)));
		}

		return new Pascal(cols);
	}

	protected void debug(String s, BigInteger[] arr)
	{
		System.out.print(s);
		for(BigInteger bi : arr)
			System.out.print("  " + bi);

		System.out.println("");
	}

	public String toString()
	{
		return getValue().toString();
	}

	public Pascal nextPascal()
	{
		PalidromeArray next = new PalidromeArray(ptLine.totalLength().add(BigInteger.ONE));
		BigInteger left = null;
		BigInteger right = null;
		int end = next.halfLength().intValue();
		for(int i=0; i<end; i++)
		{
			left = (i==0?BigInteger.ZERO:ptLine.get(i-1));
			right = ptLine.get(i);
			next.set(i, left.add(right));
		}

		return new Pascal(next);
	}

	public Pascal previousPascal()
	{
		PalidromeArray previous = new PalidromeArray(ptLine.totalLength().subtract(BigInteger.ONE));
		int end = previous.halfLength().intValue();
		for(int i=0; i<end; i++)
		{
			if(i==0)
			{
				previous.set(i, BigInteger.ONE);
				continue;
			}

			previous.set(i, ptLine.get(i).subtract(previous.get(i-1)));
		}

		return new Pascal(previous);
	}

	public Pascal nextPrime()
	{
		Pascal next = this;
		while(!(next = next.nextPascal()).isPrime()){}
		return next;
	}

	public Pascal previousPrime()
	{
		Pascal previous = this;
		while(!(previous = previous.previousPascal()).isPrime()){}
		return previous;
	}

	public boolean isPrime()
	{
		if(ptLine.totalLength().intValue() <= 2) return true;// 0 and 1?
		int end = ptLine.halfLength().intValue();
		for(int i=2; i<end; i++)
		{
//			if(!(ptLine.get(i).mod(ptLine.get(1)).equals(BigInteger.ZERO)))
			if(!MathUtil.isDivisible(ptLine.get(i), ptLine.get(1)))
				return false;
		}

		return true;
	}

	public boolean isComposite()
	{
		return !isPrime();
	}
}
